package leetcode.editor.cn;

import java.util.*;

//[773]滑动谜题

/**
 * string 一维数组。5 ms
 * 比 自定义的 二维数组效率高。13 ms
 */
public class SlidingPuzzle773 {
    public static void main(String[] args) {
        Solution solution = new SlidingPuzzle773().new Solution();

        int i = solution.slidingPuzzle(new int[][]{{1, 2, 3}, {4, 0, 5}});
        System.out.println("SlidingPuzzle773:main:"+i);

    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[][] neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};

        public int slidingPuzzle(int[][] board) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 2; ++i) {
                for (int j = 0; j < 3; ++j) {
                    sb.append(board[i][j]);
                }
            }
            String initial = sb.toString();
            if ("123450".equals(initial)) {
                return 0;
            }

            int step = 0;
            Queue<String> queue = new LinkedList<String>();
            queue.offer(initial);
            Set<String> visited = new HashSet<String>();
            visited.add(initial);

            while (!queue.isEmpty()) {
                ++step;
                int size = queue.size();
                for (int i = 0; i < size; ++i) {
                    String curStr = queue.poll();
                    for (String nextStr : getNext(curStr)) {
                        if (!visited.contains(nextStr)) {
                            if ("123450".equals(nextStr)) {
                                return step;
                            }
                            queue.offer(nextStr);
                            visited.add(nextStr);
                        }
                    }
                }
            }

            return -1;
        }

        //DFS str 得到下一个 位置。
        public List<String> getNext(String curStr) {
            List<String> ret = new ArrayList<String>();
            char[] array = curStr.toCharArray();
            int x = curStr.indexOf('0');
            for (int y : neighbors[x]) {
                swap(array, x, y);
                ret.add(new String(array));//新的 string
                swap(array, x, y);//还原，下次 for 再次使用。
            }
            return ret;
        }

        public void swap(char[] array, int x, int y) {
            char temp = array[x];
            array[x] = array[y];
            array[y] = temp;
        }


        //优化反向。数组 二维 -》1纬。
        // 遍历反向。
        String resStr = "123450";
        //BFS
        int[][] moveAble = {
                {1, 3},
                {0, 4, 2},
                {1, 5},
                {0, 4},
                {3, 1, 5},
                {4, 2}
        };

        public int slidingPuzzleBFS(int[][] board) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < board.length; i++) {
                sb.append(board[i][0]);
                sb.append(board[i][1]);
                sb.append(board[i][2]);
            }
            Set<String> visited = new HashSet<>();
            String initStr = sb.toString();
            if (resStr.equals(initStr)) return 0;
            visited.add(initStr);

            Queue<int[][]> queue = new LinkedList<>();
            queue.add(board);
            int step = 0;
            while (!queue.isEmpty()) {

                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[][] cur = queue.poll();

                    List<int[][]> moveList = getMoveList(cur);

                    for (int j = 0; j < moveList.size(); j++) {
                        StringBuilder sb2 = new StringBuilder();
                        int[][] nextStr = moveList.get(j);
                        for (int k = 0; k < 2; k++) {
                            sb2.append(nextStr[k][0]);
                            sb2.append(nextStr[k][1]);
                            sb2.append(nextStr[k][2]);
                        }
                        String nextS = sb2.toString();
                        if (resStr.equals(nextS)) return step + 1;
                        if (!visited.contains(nextS)) {
                            queue.add(nextStr);
                            visited.add(nextS);
                        }
                    }

                }
                step++;
            }

            return -1;
        }

        private List<int[][]> getMoveList(int[][] cur) {
            List<int[][]> list = new ArrayList<>(4);
            int zeroIndex = 0;
            int originRow = 0;
            int originCol = 0;
            a:for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 3; j++) {
                    if (0 == cur[i][j]) {
                        originRow = i;
                        originCol = j;
                        zeroIndex = i * 3 + j;
                        break a;
                    }
                }
            }

            //swip
            int[] swipIndexs = moveAble[zeroIndex];
            for (int i = 0; i < swipIndexs.length; i++) {
                int[][] clone = new int[2][3];
                for (int j = 0; j < 2; j++) {
                    for (int k = 0; k < 3; k++) {
                        clone[j][k] = cur[j][k];
                    }
                }
                int swipIn = swipIndexs[i];
                int row = swipIn / 3;
                int col = swipIn % 3;
                int origin = clone[row][col];
                clone[row][col] = 0;
                clone[originRow][originCol] = origin;
                list.add(clone);
            }

            return list;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}